package LeetCode;

public class Code96_numTrees {
    // 动态规划，以一个节点为根，左子树种树*右子树种数，累加
    // dp[i]指的是i个节点一共的种数
    public int numTrees(int n) {
        int[] dp = new int[n+1];
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                dp[i] += dp[j] * dp[i-j-1];
            }
        }

        return dp[n];
    }

    public static void main(String[] args) {
        Code96_numTrees code96_numTrees = new Code96_numTrees();
        System.out.println(code96_numTrees.numTrees(3));
    }
}
